//==============================================================================
//
//              DTree - the tree collection in ofc-library
//
//               Copyright (C) 2003  Dick van Oudheusden
//  
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 3 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free
// Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
//
//==============================================================================
// 
//  $Date: 2008-08-05 16:29:04 $ $Revision: 1.13 $
//
//==============================================================================

#include "ofc/DTree.h"


#if _INTERFACE_

#include "ofc/config.h"


typedef struct _DTreeNode
{
  id                     _object;        // the stored object
  struct _DTreeNode     *_parent;        // the parent node
  struct _DTreeNode     *_children;      // the (first) child node
  struct _DTreeNode     *_next;          // the next node 
  struct _DTreeNode     *_prev;          // the previous ode
  int                    _path;          // the path during iterating
} DTreeNode;

//
// The tree class implements a n-tree collection. It stores objects in a 
// tree of nodes. Because there is no key or index available to store and
// remove the objects, the objects can only be stored, inserted and removed 
// by the tree iterator: @class(DTreeIterator). 
//
// @example
// #include <stdio.h>
// #include "ofc/DTree.h"
// #include "ofc/DText.h"
// 
// int main(int argc, char *argv[])
// {
//   DTree         *tree = [DTree         new  ];
//   DTreeIterator *iter = [DTreeIterator alloc];
//   DText         *str1;
//   DText         *str2;
//   int            level;
// 
//   [iter init :tree];                   // Init the iterator with the tree
// 
//   str1 = [DText new]; [str1 set :"root"];
//   [iter append :str1];                 // Set the root
//     
//   str1 = [DText new]; [str1 set :"child1"];
//   [iter append :str1];                 // Append a child to the root and ..
//   [iter parent];                       // .. move the iterator back to the root
// 
//   str1 = [DText new]; [str1 set :"child2"]; // Append again a child to the root and ..
//   [iter append :str1];                 // .. keep the iterator on the child
// 
//   str1 = [DText new]; [str1 set :"child21"]; // Append a child for the chilld
//   [iter append :str1];
// 
//   str1 = [DText new]; [str1 set :"child22"]; // Append another child
//   [iter after :str1];
// 
//   [iter parent];                       // Move iter back to level 2
// 
//   str1 = [DText new]; [str1 set :"child4"];
//   [iter after :str1];                  // Append after the child a new child
// 
//   str2 = [DText new]; [str2 set :"child3"];
//   [iter before :str2];                 // Prepend before the child a new child
// 
//   printf("Elements in the tree:%ld.\n", [tree length]);
// 
//   printf("Tree %s child3.\n", ([tree has :str2] ? "has" : "has not")); 
// 
//   level = 1;
// 
//   str1 = [iter root];                  // Move the iter to the root
//   while (str1 != nil)
//   {
//     printf("Level:%d Element:%s.\n", level, [str1 cstring]);
// 
//     if ([iter hasChildren])            // If the node has children, than move to the first child
//     {
//       level++;
//       str1 = [iter child];
//     }
//     else if ([iter isLast])            // If all children done, than move to the next of the parent
//     {
//       level--;
//       str1 = [iter parent];            
//       if (str1 != nil)
//         str1 = [iter next];
//     }
//     else
//     {
//       str1 = [iter next];              // Else next child
//     }
//   }
// 
//   [iter free];                         // Cleanup
//   [tree free];
// 
//   return 0;
// }
//

@interface DTree : DObject
{
@private
  DTreeNode     *_root;          // the root of the tree
  long           _length;        // the number of nodes in the tree
}

#endif



@implementation DTree


#if _PRIVATE_

static const int DTR_NONE  = 0;
static const int DTR_NEXT  = 1;
static const int DTR_CHILD = 2;


static DTreeNode *getRoot(DTree *tree)
{
  return (tree->_root);
}

static void setRoot(DTree *tree, DTreeNode *root)
{
  tree->_root = root;
}

static DTreeNode *newNode(DTree *tree)
{
  DTreeNode *node = (DTreeNode *) objc_malloc(sizeof(DTreeNode));

  node->_object   = nil;
  node->_parent   = NULL;
  node->_children = NULL;
  node->_next     = NULL;
  node->_prev     = NULL;
  node->_path     = DTR_NONE;
  
  (tree->_length)++;

  return node;
}

static DTreeNode *copyNode(DTree *tree, DTreeNode *orig, DTreeNode *parent)
{
  DTreeNode *node = newNode(tree);

  node->_object   = orig->_object;
  node->_parent   = parent;

  return node;
}

static void shallowFreeNode(DTree *tree, DTreeNode *node)
{
  node->_object   = nil;
  node->_parent   = NULL;
  node->_children = NULL;
  node->_next     = NULL;
  node->_prev     = NULL;
  node->_path     = DTR_NONE;
  
  (tree->_length)--;
  
  objc_free(node);
}

static void freeNode(DTree *tree, DTreeNode *node)
{
  if (node->_object != nil)
    [node->_object free];

  shallowFreeNode(tree, node);
}

#endif


//// Constructors

//
// Initialise an empty tree
//
// @return the object
//
- (DTree *) init 
{
  [super init];

  _root   = NULL;
  _length = 0L;
 
  return self;
}


//// Copy related methods

//
// Do a shallow copy of the tree object
//
// @return the object
//
- shallowCopy
{
  DTree     *copy    = [super shallowCopy];

  DTreeNode *oWalk   = _root;  // original tree
  DTreeNode *cWalk   = NULL;   // copied tree
  DTreeNode *cParent = NULL;   // copied tree
  
  
  copy->_root   = NULL;
  copy->_length = 0L;
  
  
  if (oWalk != NULL)
  {
    oWalk->_path = DTR_NONE;
    
    cWalk = copyNode(copy, oWalk, cParent);
    
    copy->_root = cWalk;
  }
 
  while (oWalk != NULL)
  {
    if ((oWalk->_path == DTR_NONE) && (oWalk->_next != NULL))
    {
      DTreeNode *node;
      
      oWalk->_path = DTR_NEXT;
      
      oWalk = oWalk->_next;

      oWalk->_path = DTR_NONE;
      
      node = copyNode(copy, oWalk, cParent);
      
      cWalk->_next = node;
      node ->_prev = cWalk;
      
      cWalk = node;
    }
    else if ((oWalk->_path != DTR_CHILD) && (oWalk->_children != NULL))
    {
      oWalk->_path = DTR_CHILD;
      
      oWalk = oWalk->_children;

      oWalk->_path = DTR_NONE;
      
      cParent = cWalk;
      
      cWalk = copyNode(copy, oWalk, cParent);
      
      cParent->_children = cWalk;
    }
    else if (oWalk->_prev != NULL)
    {
      oWalk = oWalk->_prev;
      
      cWalk = cWalk->_prev;
    }
    else
    {
      oWalk = oWalk->_parent;
      
      cWalk = cWalk->_parent;

      cParent = (cWalk != NULL) ? cWalk->_parent : NULL;
    }
  }

  return copy;
}

//
// Deepen a copied tree object
//
// @return the object
//
- deepen
{
  DTreeNode *walk    = _root;
  
  [super deepen];

  if (walk != NULL)
    walk->_path = DTR_NONE;
 
  while (walk != NULL)
  {
    if ((walk->_path == DTR_NONE) && (walk->_next != NULL))
    {
      walk->_path = DTR_NEXT;
      
      walk = walk->_next;

      walk->_path = DTR_NONE;
    }
    else if ((walk->_path != DTR_CHILD) && (walk->_children != NULL))
    {
      walk->_path = DTR_CHILD;
      
      walk = walk->_children;

      walk->_path = DTR_NONE;
    }
    else
    {
      if (walk->_object != nil)
      {
        walk->_object = [walk->_object copy];
      }
   
      walk = (walk->_prev != NULL ? walk->_prev : walk->_parent);
    }
  }
  
  return self;
}

//// Deconstructor

//
// Free the object (without the stored objects)
//
// @return the object
//
- shallowFree
{
  DTreeNode *walk = _root;
  while (walk != NULL)
  {
    if (walk->_children != NULL)
    {
      walk = walk->_children;
    }
    else if (walk->_next != NULL)
    {
      walk = walk->_next;
    }
    else
    {
      DTreeNode *prev = NULL;
      
      if (walk->_prev != NULL)
      {
        prev = walk->_prev;

        prev->_next = NULL;
      }
      else if (walk->_parent != NULL)
      {
        prev = walk->_parent;

        prev->_children = NULL;
      }
      else
      {
        _root = NULL;
      }
      
      shallowFreeNode(self, walk);

      walk = prev;
    }
  }

  [super free];
  
  return self;
}

//
// (Deep) free the object (including the stored objects)
//
// @return the object
//
- free
{
  DTreeNode *walk = _root;
  while (walk != NULL)
  {
    if (walk->_children != NULL)
    {
      walk = walk->_children;
    }
    else if (walk->_next != NULL)
    {
      walk = walk->_next;
    }
    else
    {
      DTreeNode *prev = NULL;
      
      if (walk->_prev != NULL)
      {
        prev = walk->_prev;

        prev->_next = NULL;
      }
      else if (walk->_parent != NULL)
      {
        prev = walk->_parent;

        prev->_children = NULL;
      }
      else
      {
        _root = NULL;
      }
      
      freeNode(self, walk);

      walk = prev;
    }
  }

  [super free];
  
  return self;
}


//// Member methods

//
// Return the number of objects in the tree
//
// @return the number of objects
//
- (long) length
{
  return _length;
}

//
// Check if the tree is empty
//
// @return is it
//
- (BOOL) isEmpty
{
  return (_length == 0);
}


//// Collection methods

//
// Check if the collection has a certain object
//
// @param obj      the object to be found
//
// @return has it ?
//
- (BOOL) has :(id) obj
{
  DTreeNode *walk = _root;

  if (walk != NULL) 
    walk->_path = DTR_NONE;
  
  while (walk != NULL)
  {
    if ((walk->_path == DTR_NONE) && (walk->_next != NULL))
    {
      walk->_path = DTR_NEXT;
      
      walk = walk->_next;

      walk->_path = DTR_NONE;
    }
    else if ((walk->_path != DTR_CHILD) && (walk->_children != NULL))
    {
      walk->_path = DTR_CHILD;
      
      walk = walk->_children;

      walk->_path = DTR_NONE;
    }
    else
    {
      if (walk->_object == obj)
      {
        return YES;
      }
   
      walk = (walk->_prev != NULL ? walk->_prev : walk->_parent);
    }
  }

  return NO;
}

//
// Count the number of occurences of an object
//
// @param obj      the object to be counted
//
// @return the number of occurences
//
- (long) count :(id) obj
{
  DTreeNode *walk    = _root;
  long       counter = 0L;

  if (walk != NULL)
    walk->_path = DTR_NONE;
 
  while (walk != NULL)
  {
    if ((walk->_path == DTR_NONE) && (walk->_next != NULL))
    {
      walk->_path = DTR_NEXT;
      
      walk = walk->_next;

      walk->_path = DTR_NONE;
    }
    else if ((walk->_path != DTR_CHILD) && (walk->_children != NULL))
    {
      walk->_path = DTR_CHILD;
      
      walk = walk->_children;

      walk->_path = DTR_NONE;
    }
    else
    {
      if (walk->_object == obj)
      {
        counter++;
      }
   
      walk = (walk->_prev != NULL ? walk->_prev : walk->_parent);
    }
  }

  return counter;
}

//
// Perform a method for each object in the tree
//
// @param sel      the selector 
//
// @return the object
//
- (DTree *) each :(SEL) sel
{
  DTreeNode *walk = _root;

  if (walk != NULL)
    walk->_path = DTR_NONE;
 
  while (walk != NULL)
  {
    if ((walk->_path == DTR_NONE) && (walk->_next != NULL))
    {
      walk->_path = DTR_NEXT;
      
      walk = walk->_next;

      walk->_path = DTR_NONE;
    }
    else if ((walk->_path != DTR_CHILD) && (walk->_children != NULL))
    {
      walk->_path = DTR_CHILD;
      
      walk = walk->_children;

      walk->_path = DTR_NONE;
    }
    else
    {
      if (walk->_object != nil)
      {
        [walk->_object perform :sel];
      }
   
      walk = (walk->_prev != NULL ? walk->_prev : walk->_parent);
    }
  }

  return self;
}

@end



#if _INTERFACE_

//
// The tree iterator class implements an iterator on a n-tree collection. 
// Because there is no key or index available to store and remove the objects, 
// the objects can only be stored and removed by this iterator.
//
// @example
// #include <stdio.h>
// #include "ofc/DTree.h"
// #include "ofc/DText.h"
// 
// int main(int argc, char *argv[])
// {
//   DTree         *tree = [DTree         new  ];
//   DTreeIterator *iter = [DTreeIterator alloc];
//   DText         *str1;
//   DText         *str2;
//   int            level;
// 
//   [iter init :tree];                   // Init the iterator with the tree
// 
//   str1 = [DText new]; [str1 set :"root"];
//   [iter append :str1];                 // Set the root
//     
//   str1 = [DText new]; [str1 set :"child1"];
//   [iter append :str1];                 // Append a child to the root and ..
//   [iter parent];                       // .. move the iterator back to the root
// 
//   str1 = [DText new]; [str1 set :"child2"]; // Append again a child to the root and ..
//   [iter append :str1];                 // .. keep the iterator on the child
// 
//   str1 = [DText new]; [str1 set :"child21"]; // Append a child for the chilld
//   [iter append :str1];
// 
//   str1 = [DText new]; [str1 set :"child22"]; // Append another child
//   [iter after :str1];
// 
//   [iter parent];                       // Move iter back to level 2
// 
//   str1 = [DText new]; [str1 set :"child4"];
//   [iter after :str1];                  // Append after the child a new child
// 
//   str2 = [DText new]; [str2 set :"child3"];
//   [iter before :str2];                 // Prepend before the child a new child
// 
//   printf("Elements in the tree:%ld.\n", [tree length]);
// 
//   printf("Tree %s child3.\n", ([tree has :str2] ? "has" : "has not")); 
// 
//   level = 1;
// 
//   str1 = [iter root];                  // Move the iter to the root
//   while (str1 != nil)
//   {
//     printf("Level:%d Element:%s.\n", level, [str1 cstring]);
// 
//     if ([iter hasChildren])            // If the node has children, than move to the first child
//     {
//       level++;
//       str1 = [iter child];
//     }
//     else if ([iter isLast])            // If all children done, than move to the next of the parent
//     {
//       level--;
//       str1 = [iter parent];            
//       if (str1 != nil)
//         str1 = [iter next];
//     }
//     else
//     {
//       str1 = [iter next];              // Else next child
//     }
//   }
// 
//   [iter free];                         // Cleanup
//   [tree free];
// 
//   return 0;
// }
//

@interface DTreeIterator : DObject
{
@private
  DTree         *_tree;          // the tree
  DTreeNode     *_node;          // the current node
}

#endif



@implementation DTreeIterator


//// Constructors

//
// Initialise an empty iterator
//
// @return the object
//
- (DTreeIterator *) init 
{
  [self init :nil];

  return self;
}

//
// Initialise the iterator with a tree (iterator is moved to the root)
//
// @param tree     the tree for the iterator (<> nil)
//
// @return the object
//
- (DTreeIterator *) init :(DTree *) tree
{
  [super init];

  _tree = tree;
  
  if (_tree == nil)
  {
    _node = NULL;

    WARNING(DW_OBJECT_NOT_INIT, "init :tree");
  }
  else
  {
    _node = getRoot(_tree);
  }

  return self;
}


//// Movement methods

//
// Move to the first child (in the list of childs)
//
// @return the object of the first child (or nil)
//
- (id) first
{
  if (_node != NULL)
  {
    while (_node->_prev != NULL)
    {
      _node = _node->_prev;
    }
    return _node->_object;
  }
  else
    return nil;
}

//
// Move to the next child (in the list of childs)
//
// @return the object of the next child (or nil)
//
- (id) next
{
  if ((_node != NULL) && (_node->_next != NULL))
  {
    _node = _node->_next;

    return _node->_object;
  }

  return nil;
}

//
// Move to the previous child (in the list of childs)
//
// @return the object of the previous child (or nil)
//
- (id) prev
{
  if ((_node != NULL) && (_node->_prev != NULL))
  {
    _node = _node->_prev;

    return _node->_object;
  }

  return nil;
}

//
// Move to the last child (in the list of childs)
//
// @return the object in the last node (or nil)
//
- (id) last
{
  if (_node != NULL)
  {
    while (_node->_next != NULL)
    {
      _node = _node->_next;
    }
    return _node->_object;
  }
  else
    return nil;
}

//
// Move the iterator to a certain object. The object is searched
// from the root. If the object is not found, the iterator
// remains on the same location as before calling this method.
// If the object is found, the iterator is moved to this object.
//
// @param obj      the object to be found
//
// @return is it found ?
//
- (BOOL) move :(id) obj
{
  DTreeNode *walk = NULL;
  
  if (_tree != nil)
  {
    walk = getRoot(_tree);
  }

  if (walk != NULL) 
    walk->_path = DTR_NONE;
  
  while (walk != NULL)
  {
    if ((walk->_path == DTR_NONE) && (walk->_next != NULL))
    {
      walk->_path = DTR_NEXT;
      
      walk = walk->_next;

      walk->_path = DTR_NONE;
    }
    else if ((walk->_path != DTR_CHILD) && (walk->_children != NULL))
    {
      walk->_path = DTR_CHILD;
      
      walk = walk->_children;

      walk->_path = DTR_NONE;
    }
    else
    {
      if (walk->_object == obj)
      {
        _node = walk;
        
        return YES;
      }
   
      walk = (walk->_prev != NULL ? walk->_prev : walk->_parent);
    }
  }

  return NO;
}

//
// Move to the root
//
// @return the object in the root (or nil)
//
- (id) root
{
  _node = NULL;
  
  if (_tree != nil)
  {
    _node = getRoot(_tree);
  }
  
  return (_node == NULL) ? nil : _node->_object;
}

//
// Move to the parent (for the current child)
//
// @return the object in the parent (or nil)
//
- (id) parent
{
  if ((_node != NULL) && (_node->_parent != NULL))
  {
    _node = _node->_parent;
      
    return _node->_object;
  }

  return nil;
}

//
// Move to the first child (for the current parent)
//
// @return the object in the first child (or nil)
//
- (id) child
{
  if ((_node != NULL) && (_node->_children != NULL))
  {
    _node = _node->_children;
      
    return _node->_object;
  }

  return nil;
}


//// Test methods

//
// Test if the iterator is on the first child (in the list of childs)
//
// @return is it ?
//
- (BOOL) isFirst
{
  if (_node != NULL)
  {
    return (_node->_prev == NULL);
  }
  else
    return NO;
}

//
// Test if the iterator is on the last child (in the list of childs)
//
// @return is it ?
//
- (BOOL) isLast
{
  if (_node != NULL)
  {
    return (_node->_next == NULL);
  }
  else
    return NO;
}

//
// Test if the iterator is on the root 
//
// @return is it ?
//
- (BOOL) isRoot
{
  if (_node != NULL)
  {
    return (getRoot(_tree) == _node);
  }
  else
    return NO;
}

//
// Test if the iterator is on a parent with children
//
// @return has it ?
//
- (BOOL) hasChildren
{
  if (_node != NULL)
  {
    return (_node->_children != NULL);
  }
  else
    return NO;
}


//// Stored object methods

//
// Set the object in the current node
//
// @param obj      the object to be set
//
// @return the previous object in the node
//
- (id) object :(id) obj
{
  if (_node != NULL)
  {
    id origin = (_node->_object);

    _node->_object = obj;

    return origin;
  }
  else
    return nil;
}

//
// Get the object in the current node
//
// @return the object in the node (or nil)
//
- (id) object
{
  if (_node != NULL)
  {
    return _node->_object;
  }
  else
    return nil;
}


//// Add/Insert/Remove methods

//
// Prepend a child to the current (parent) node (iterator is moved to this new child)
//
// @param obj      the object to be added as child
//
// @return the object
//
- (DTreeIterator *) prepend :(id) obj
{
  if (_node != NULL)
  {
    DTreeNode *child = newNode(_tree);

    child->_parent = _node;
    child->_object = obj;
        
    if (_node->_children != NULL)
    {
      child->_next = _node->_children;

      _node->_children->_prev = child;
    }
    _node->_children = child;
    
    _node = child;
  }
  else if (_tree == nil)
  {
    WARNING(DW_OBJECT_NOT_INIT, "init :tree");
  }
  else if (getRoot(_tree) == NULL)
  {
    DTreeNode *child = newNode(_tree);

    child->_object = obj;

    setRoot(_tree, child);

    _node = child;
  }
  else
  {
    WARNING(DW_UNEXPECTED_ERROR, " no parent selected");
  }

  return self;
}

//
// Append a child to current (parent) node (iterator is moved to new child)
//
// @param obj      the object to be added as child
//
// @return the object
//
- (DTreeIterator *) append :(id) obj
{
  if (_node != NULL)
  {
    DTreeNode *child = newNode(_tree);

    child->_parent = _node;
    child->_object = obj;
        
    if (_node->_children != NULL)
    {
      DTreeNode *walk = _node->_children;
      
      while (walk->_next != NULL)
        walk = walk->_next;
      
      walk->_next  = child;
      child->_prev = walk;
    }
    else    
      _node->_children = child;

    _node = child;
  }
  else if (_tree == nil)
  {
    WARNING(DW_OBJECT_NOT_INIT, "init :tree");
  }
  else if (getRoot(_tree) == NULL)
  {
    DTreeNode *child = newNode(_tree);

    child->_object = obj;

    setRoot(_tree, child);

    _node = child;
  }
  else
  {
    WARNING(DW_UNEXPECTED_ERROR, " no parent selected");
  }

  return self;
}

//
// Insert a new child before current (child) node (iterator is moved to new child)
//
// @param obj      the object to be added as child
//
// @return the object
//
- (DTreeIterator *) before :(id) obj
{
  if (_node != NULL)
  {
    DTreeNode *child = newNode(_tree);

    child->_parent = _node->_parent;
    child->_object = obj;

    child->_prev   = _node->_prev;
    child->_next   = _node;
    
    if (_node->_prev != NULL)
      _node->_prev->_next = child;
    
    _node->_prev   = child;

    if (_node->_parent->_children == _node)
      _node->_parent->_children = child;
    
    _node = child;
  }
  else
  {
    WARNING(DW_UNEXPECTED_ERROR, " no child selected");
  }

  return self;
}

//
// Insert a new child after current (child) node (iterator is moved to new child)
//
// @param obj      the object to be added as child
//
// @return the object
//
- (DTreeIterator *) after :(id) obj
{
  if (_node != NULL)
  {
    DTreeNode *child = newNode(_tree);

    child->_parent = _node->_parent;
    child->_object = obj;

    child->_next   = _node->_next;
    child->_prev   = _node;
    
    if (_node->_next != NULL)
      _node->_next->_prev = child;
    
    _node->_next   = child;

    _node = child;
  }
  else
  {
    WARNING(DW_UNEXPECTED_ERROR, " no child selected");
  }

  return self;
}

//
// Remove the current node 
// Note: only if current node has no children
// Note: iterator moves to 1. the next child or 2. the previous child or 3. the parent
//
// @return the object from the current node (or nil)
//
//
- (id) remove
{
  id obj = nil;

  if (_node == NULL)
  {
    WARNING(DW_UNEXPECTED_ERROR, " no node selected");
  }
  else if (_node->_children == NULL)
  {
    DTreeNode *origin = _node;

    obj = _node->_object;
    
    if (_node->_next != NULL)
      _node->_next->_prev = _node->_prev;
    if (_node->_prev != NULL)
      _node->_prev->_next = _node->_next;
      
    if (_node->_next != NULL)
    {
      _node = _node->_next;
    }
    else if (_node->_prev != NULL)
    {
      _node = _node->_prev;
    }
    else
    {
      _node = _node->_parent;
     
      if (_node != NULL) 
        _node->_children = NULL;
    }
    if ((origin->_parent != NULL) && (origin->_parent->_children == origin) && (_node != NULL))
    {
      origin->_parent->_children = _node;
    }
    
    if (getRoot(_tree) == origin)
      setRoot(_tree, _node);
      

    shallowFreeNode(_tree, origin);
  }

  return obj;
}

@end
       
/*==========================================================================*/

